package com.mdnote.practice.dfs_bfs;


import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/17 0017
 * @description 最小基因变化
 */
public class LeetCode433 {


    public static void main(String[] args) {
        LeetCode433 leetCode433 = new LeetCode433();
        leetCode433.minMutation("AACCGGTT", "AAACGGTA", new String[]{"AACCGGTA", "AACCGCTA", "AAACGGTA"});
    }
    public int minMutation(String start, String end, String[] bank) {
        // 和单词接龙相似
        int step = bfs(start, end, bank);
        System.out.println(step);
        return step;
    }

    private int bfs(String start, String end, String[] bank) {

        HashSet<String> bankSet = new HashSet<>(Arrays.asList(bank));
        if (!bankSet.contains(end)) {
            return -1;
        }

        LinkedList<String> queue = new LinkedList<>();
        queue.add(start);

        char[] selectArray = {'A', 'C', 'G', 'T'};

        int step = 0;
        HashSet<String> visited = new HashSet<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String eachString = queue.removeFirst();
                char[] chars = eachString.toCharArray();
                char[] originChar = Arrays.copyOf(chars, chars.length);
                for (int j = 0; j < chars.length; j++) {
                    for (char c : selectArray) {
                        chars[j] = c;
                        String newString = new String(chars);
                        if (newString.equals(end)) {
                            return step + 1;
                        }
                        if (bankSet.contains(newString) && !visited.contains(newString)) {
                            visited.add(newString);
                            queue.addLast(newString);
                        }
                    }
                    chars[j] = originChar[j];
                }
            }
            step++;
        }
        return -1;
    }


}
